/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
export var findRightInterval = function (intervals) {
  const ans = new Array(intervals.length).fill(-1)
  for (let i = 0; i < intervals.length - 1; i++) {
    const item = intervals[i]
    for (let j = i; j < intervals.length; j++) {
      const itemJ = intervals[j]
      if (item[1] <= itemJ[0])
        ans[i] = ans[i] === -1 || itemJ[0] < intervals[ans[i]][0] ? j : ans[i]
      if (itemJ[1] <= item[0]) ans[j] = ans[j] === -1 || item[0] < intervals[ans[j]][0] ? i : ans[j]
    }
  }
  return ans
}

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
export var findRightInterval2 = function (intervals) {
  const ans = new Array(intervals.length).fill(-1)
  const startIntervals = intervals.map((item, index) => [item[0], index])
  startIntervals.sort((a, b) => a[0] - b[0])
  for (let i = 0; i < intervals.length; i++) {
    const item = intervals[i]
    // 二分查找
    let [left, right, target] = [0, intervals.length - 1, -1]
    while (left <= right) {
      const mid = (left + right) >> 1
      if (startIntervals[mid][0] >= item[1]) {
        target = startIntervals[mid][1]
        right = mid - 1
      } else left = mid + 1
    }
    ans[i] = target
  }
  return ans
}
